package linkedlist

type Node struct {
	Val  int
	Next *Node
}

// Problem Definition:
// https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a?tpId=117&tqId=37812&rp=1
// https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

func ysf(n, m int) int {
	head := &Node{Val: 1}
	cur := head
	for i := 2; i <= n; i++ {
		n := &Node{Val: i}
		cur.Next = n
		cur = n
	}

	cur.Next = head
	pre := cur
	cur = head

	for cur != nil && cur.Next != cur {
		cnt := 0
		for {
			cnt++
			if cnt == m {
				pre.Next = cur.Next
				cur = cur.Next
				break
			}

			pre, cur = cur, cur.Next
		}
	}

	return cur.Val
}

func ysf1(n, m int) int {
	last := 0
	for i := 2; i <= n; i++ {
		last = (last + m) % i
	}

	return last + 1
}

func ysf2(n, m int) int {
	if n < 1 || m < 1 {
		return 0
	}

	if n == 1 {
		return n
	}

	return (ysf2(n-1, m)+m-1)%n + 1
}
